题解 P3480 【[POI2009]KAM-Pebbles】

发表于 | 更新于

$Description$

有$N$堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。

$Solution$

题目要求每堆石子个数都不少于前一堆的石子个数，可以理解为差分数组$c$必须每项都$\geqslant 0$,而每次操作在第$i$堆取了$k$个石子，就相当于$c_{i}-=k,c_{i+1}+=k$,这就类似于阶梯$nim$了，不过由于方向相反，所以阶梯$nim$要反着做

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define N 300007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int c[N],w[N];
signed main(){
    int T=read();
    while (T--){
        int n=read(),ans=0;
        for (int i=1;i<=n;++i)w[i]=read(),c[i]=w[i]-w[i-1];
        for (int i=n;i;--i)
            if ((n-i+1)&1)
                ans^=c[i];
        if (ans)puts("TAK");
        else puts("NIE");
    }
}